package cn.z2huo.datastructure.tree.traverseBinaryTree;

import cn.z2huo.datastructure.tree.node.Node;

/**
 * 构建二叉树时的一些工具
 *
 * @author bouncyslime
 * @date 2021/1/17
 */
public class BinaryTreeUtils {

    /**
     * 根据数组递归构造二叉树
     * 二叉树的顺序存储结构，用数组依次自上而下、自左至右存储完全二叉树上的结点元素
     * 数组下标i代表完全二叉树上编号为i+1的结点元素（完全二叉树根结点编号为1）
     *
     * @param array 包含二叉树各个结点的数组
     * @return 二叉树根节点
     */
    public static <T> Node<T> createBinaryTreeFromArray(T[] array) {
        Node<T> root;
        if (array == null || array.length == 0) {
            root = null;
        } else {
            root = createBinaryTree(new Node<>(array[0]), array, 0);
        }
        return root;
    }

    /**
     * 根据array中的数据，从根结点递归地构造二叉树
     * 利用了完全二叉树的性质：从根结点按层序从左到右从1开始编号，任一结点i，其左孩子结点序号为2i，其右孩子结点序号为2i+1
     *
     * @param root     根结点
     * @param array    数组
     * @param position root对应的数组下标
     */
    private static <T> Node<T> createBinaryTree(Node<T> root, T[] array, int position) {
        if (root.getLeft() == null
                && array.length > 2 * position + 1
                && array[2 * position + 1] != null) {
            root.setLeft(new Node<>(array[2 * position + 1]));
            createBinaryTree(root.getLeft(), array, 2 * position + 1);
        }
        if (root.getRight() == null
                && array.length > 2 * position + 2
                && array[2 * position + 2] != null) {
            root.setRight(new Node<>(array[2 * position + 2]));
            createBinaryTree(root.getRight(), array, 2 * position + 2);
        }
        return root;
    }
}
